package sword;

/**
 * @Author: 海琳琦
 * @Date: 2022/5/30 11:31
 * https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
 */
public class Title03 {

    public int findRepeatNumber(int[] nums) {
        //哈希方法
//        Set<Integer> set = new HashSet<>();
//        for (int i = 0; i < nums.length; i++) {
//            if (!set.add(nums[i])) {
//                return nums[i];
//            }
//        }
//        return -1;


        //因为数组中元素值的范围为0 - n-1，原地hash
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                int temp = nums[nums[i]];
                if (temp == nums[i]) {
                    return nums[i];
                }else{
                    nums[nums[i]] = nums[i];
                    nums[i] = temp;
                    i--;
                }
            }
        }
        return -1;
    }



    public static void main(String[] args) {

    }
}
